package com.cat.gridChart;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/01-matrix/description/
 * @create 2025/9/7 20:10
 * @since JDK17
 */

public class Solution14 {
    static int[][] q = new int[10010][2];
    int[][] ans, d = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    boolean[][] vis;

    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length, m = mat[0].length, h = 0, t = 0;
        vis = new boolean[n][m];
        ans = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == 0) {
                    q[t++] = new int[] { i, j };
                    vis[i][j] = true;
                }
            }
        }

        while (h < t) {
            var p = q[h++];
            for (int i = 0; i < 4; i++) {
                int nx = p[0] + d[i][0], ny = p[1] + d[i][1];
                if (nx == -1 || nx == n || ny == -1 || ny == m || vis[nx][ny]) {
                    continue;
                }
                ans[nx][ny] = ans[p[0]][p[1]] + 1; // 上一个位置加一
                vis[nx][ny] = true;
                q[t++] = new int[] { nx, ny };
            }
        }

        return ans;
    }
}
